# TODO
#  * Parallel reporting
#  * Argument parsing
#  * sigon/off counts
#  - randomness
#  - timeouts
#  - .sage, .spyx, ...
#      load(...)
#  * optional
#  * setup (plotting, ...)
#  * timing
#      * record
#      * compare
#      * playback


import json, hashlib, multiprocessing, random, glob, re, optparse, os, sys, time, traceback, warnings
from collections import defaultdict
import dbwrap
import custom_doctest as doctest
from util import *

from sage.misc.preparser import preparse, strip_string_literals
import sage.misc.randstate as randstate
from sage.misc.misc import walltime, cputime

float_regex = re.compile('[+-]?((\d*\.?\d+)|(\d+\.?))([eE][+-]?\d+)?') 
whitespace = re.compile("\s*")
triple_quotes = re.compile("\s*[rRuU]*((''')|(\"\"\"))")
name_regex = re.compile(r".*\s(\w+)([(].*)?:")
sage_prompt = re.compile(r"^(\s*)sage: ", re.M)
indent_regex = re.compile(r"\s*")
whitespace_regex = re.compile(r"\s+")
sage_library_regex = re.compile(r"/devel/sage.*/(sage/.*)")
random_marker = re.compile('#.*random', re.I)
bitness_marker = re.compile('#.*(32|64)-bit')
bitness_value = '64' if sys.maxint > (1 << 32) else '32'
optional_regex = re.compile(r'(long time|not implemented|not tested|known bug)|(optional\s*[:-]?\s*(\w*))')

def parse_optional_tags(string):
    first_line = string.split('\n', 1)[0]
    if '#' not in first_line:
        return set()
    comment = first_line[first_line.find('#'):]
    return set(m.group(1) or m.group(3) for m in optional_regex.finditer(comment.lower()))

def get_source(example):
    return getattr(example, 'sage_source', example.source)

def pre_hash(s):
    return "%s:%s" % (len(s), s)

def reduce_hex(fingerprints):
    """
    Returns a symmetric function of the arguments as hex strings.
    """
    from operator import xor
    res = reduce(xor, (int(x, 16) for x in fingerprints), 0)
    if res < 0:
        res += 1 << 128
    return "%032x" % res

def normalize_source(source):
    """
    >>> list(normalize_source('  a  +\tb\n\nc'))
    ['  a + b', 'c']
    >>> list(normalize_source('for a in range(10):a; b # comment'))
    ['for a in range(10)', '    a', '    b']
    >>> list(normalize_source('for a in range(10)\n a; b'))
    ['for a in range(10)', ' a', ' b']


    >>> list(normalize_source('  for a in range(10)\n a; b'))
    ['  for a in range(10)', '   a', '   b']
    """
    stripped, literals, _ = strip_string_literals(source)
    for line in stripped.split('\n'):
        if '#' in line:
            line = line[:line.index('#')]
        indent = indent_regex.match(line).group()
        if indent == line:
            continue
        line = whitespace_regex.sub(r' ', line.strip())
        if ':' in line:
            ix = line.index(':')
            yield indent + line[:ix] % literals
            for body in normalize_source("    " + line[ix+1:].strip()):
                yield indent + body % literals
        else:
            for part in line.split(';'):
                part = part.strip()
                if part:
                    yield indent + part % literals

class NestedName:
    """
    Class used to construct fully qualified names based on indentation level.
    """
    def __init__(self, base):
        self.all = [base]
    def __setitem__(self, index, value):
        while len(self.all) <= index:
            self.all.append(None)
        self.all[index+1:] = [value]
    def __str__(self):
        return '.'.join(a for a in self.all if a is not None)


# Inheritance rather then delegation as globals() must be a dict
class RecordingDict(dict):

    def __init__(self, *args, **kwds):
        dict.__init__(self, *args, **kwds)
        self.start()

    def start(self):
        self.set = []
        self.got = []

    def __getitem__(self, name):
        if name not in self.set:
            self.got.append(name)
        return dict.__getitem__(self, name)

    def __setitem__(self, name, value):
        self.set.append(name)
        dict.__setitem__(self, name, value)
    
    def __delitem__(self, name):
        self.set.append(name)
        dict.__delitem__(self, name)
    
    def get(self, name, *args):
        if name not in self.set:
            self.got.append(name)
        return dict.get(self, name, args)
    
    def copy(self):
        return RecordingDict(dict.copy(self))


class MarkedOutput(str):
    random = False
    rel_tol = 0
    abs_tol = 0
    def update(self, **kwds):
        self.__dict__.update(kwds)
        return self

class Timer:
    def start(self):
        self.cputime = cputime()
        self.walltime = walltime()
        return self
    def stop(self):
        self.cputime = cputime(self.cputime)
        self.walltime = walltime(self.walltime)
        return self
    def annotate(self, object):
        object.cputime = self.cputime
        object.walltime = self.walltime
    def __repr__(self):
        return str(self)
    def __str__(self):
        return str(self.__dict__)


class SageDocTestParser(doctest.DocTestParser):

    def __init__(self, long=False, optional_tags=(), optional_only=False):
        self.optional_tags = set(optional_tags)
        self.optional_only = False
        
    def parse(self, string, *args):
        # Hack for non-standard backslash line escapes accepted by the current
        # doctest system.
        old_string = ""
        while string != old_string:
            old_string, string = string, re.sub("(\\s*)sage:(.*)\\\\\ *\n\\s*([^. ])", r"\1sage:\2 \3", string)

        string = sage_prompt.sub(r"\1>>> sage: ", string)
        res = doctest.DocTestParser.parse(self, string, *args)
        filtered = []
        for item in res:
            if isinstance(item, doctest.Example):
                optional_tags = parse_optional_tags(item.source)
                if optional_tags:
                    if not optional_tags.issubset(self.optional_tags):
                        continue
                elif self.optional_only:
                    continue
                if random_marker.search(item.source):
                    item.want = MarkedOutput(item.want).update(random=True)
                if item.source.startswith("sage: "):
                    item.sage_source = item.source[6:]
                    if item.sage_source.lstrip().startswith('#'):
                        continue
                    item.source = preparse(item.sage_source) # + "\n#" +  item.sage_source.replace('\n', '\n#')[:-1]
            filtered.append(item)
        return filtered

def warning_function(file):
    def doctest_showwarning(message, category, filename, lineno, file=file, line=None):
        try:
            file.write(warnings.formatwarning(message, category, 'doctest', lineno, line))
        except IOError:
            pass # the file (probably stdout) is invalid
    return doctest_showwarning

class OriginalSource:
    """
    Context swapping out the pre-parsed source with the original for better reporting.
    """
    def __init__(self, example):
        self.example = example
    def __enter__(self):
        if hasattr(self.example, 'sage_source'):
            self.old_source, self.example.source = self.example.source, self.example.sage_source
    def __exit__(self, *args):
        if hasattr(self.example, 'sage_source'):
            self.example.source = self.old_source

class SageDocTestRunner(doctest.DocTestRunner):

    def __init__(self, *args, **kwds):
        doctest.DocTestRunner.__init__(self, *args, **kwds)
        self.history = []
        self.references = []
        self.setters = {}
        self.running_global_digest = hashlib.md5()

    def run(self, *args, **kwds):
        self.setters = {}
        randstate.set_random_seed(long(0))
        warnings.showwarning = warning_function(self._fakeout)
        self.running_doctest_digest = hashlib.md5()
        return doctest.DocTestRunner.run(self, *args, **kwds)
    
    def update_digests(self, example):
        s = pre_hash(get_source(example))
        self.running_global_digest.update(s)
        self.running_doctest_digest.update(s)
        if example.predecessors is not None:
            digest = hashlib.md5(s)
            digest.update(reduce_hex(e.running_state for e in example.predecessors))
            example.running_state = digest.hexdigest()

    def execute(self, example, compiled, globs):
#        if True:
#            exec compiled in globs
#            return
        if isinstance(globs, RecordingDict):
            globs.start()
        example.sequence_number = len(self.history)
        self.history.append(example)
        timer = Timer().start()
        
        try:
            exec compiled in globs
        finally:
            timer.stop().annotate(example)
            if isinstance(globs, RecordingDict):
                example.predecessors = []
                for name in set(globs.got):
                    ref = self.setters.get(name)
                    if ref is not None:
                        example.predecessors.append(ref)
                for name in set(globs.set):
                    self.setters[name] = example
            else:
                example.predecessors = None
            self.update_digests(example)
            example.total_state = self.running_global_digest.hexdigest()
            example.doctest_state = self.running_doctest_digest.hexdigest()

    def _failure_header(self, test, example):
        with OriginalSource(example):
            return doctest.DocTestRunner._failure_header(self, test, example)
    
    def results(self):
        # Non-pickleable items.
        self.running_global_digest = self.running_doctest_digest = self.debugger = None
        return self

class SageOutputChecker(doctest.OutputChecker):
    def check_output(self, want, got, optionflags):
        if isinstance(want, MarkedOutput):
            if want.random:
                return True
            elif want.rel_tol or want.abs_tol:
                if want.abs_tol:
                    check_tol = lambda a, b: abs(a-b) <= want.abs_tol
                else:
                    check_tol = lambda a, b: (a == b == 0) or (a*b != 0 and abs(a-b)/abs(a) + abs(b) < want.rel_tol)
                want_values = [float(g[0]) for g in float_regex.findall(want)]
                got_values = [float(g[0]) for g in float_regex.findall(got)]
                if not doctest.OutputChecker.check_output(
                        float_regex.sub('*', want), float_regex.sub('*', got), optionflags):
                    return False
                if len(want_values) != len(got_values):
                    return False
                if not all(check_tol(*ab) for ab in zip(want_values, got_values)):
                    return False
        return doctest.OutputChecker.check_output(self, want, got, optionflags)


class DoctestResults:
    def __init__(self, **kwds):
        self.__dict__.update(**kwds)

def extract_doctests_from_source(basename, source, sage_namespace):
    parser = SageDocTestParser()
    last_indent = -1
    last_line = None
    qualified_name = NestedName(basename)
    # Line-by-line parsing makes it easy to keep track of line numbers...
    
    doctests = []
    in_docstring = False
    for lineno, line in enumerate(source):
        if in_docstring:
            if triple_quotes.match(line):
                in_docstring = False
                docstring = "".join(doc)
                doctests.append(parser.get_doctest(docstring, sage_namespace, str(qualified_name), basename, start))
            else:
                bitness = bitness_marker.search(line)
                if bitness:
                    if bitness.groups()[0] != bitness_value:
                        continue
                    else:
                        line = line[:bitness.start()] + "\n"
                doc.append(line)
        else:
            if not line.strip():
                continue
            indent = whitespace.match(line).end()
            if line[indent] == '#':
                continue
            if indent > last_indent:
                if triple_quotes.match(line):
                    if last_indent >= 0:
                        name = name_regex.match(last_line)
                        if name:
                            name = name.groups()[0]
                        else:
                            name = '?'
                        qualified_name[indent] = name
                    doc = []
                    in_docstring = True
                    start = lineno
            last_line, last_indent = line, indent
    return doctests

def init_sage():
    # Do this once before forking.
    import sage.all
    sage.plot.plot; sage.plot.plot.DOCTEST_MODE=True
    sage.interfaces.quit.invalidate_all()

def apply(data):
    multiprocessing.current_process().daemon = False
    func, args, kwds = data
    return func(*args, **kwds)

def run_doctests(files, run_id, nthreads=1, **kwds):
    timer = Timer().start()
    init_sage()
    
    postscript = dict(lines=[], cputime=0, walltime=0)
    stats = {}
    # Use multiprocessing if needed.
    if nthreads > 1 and not isinstance(files, list) or len(files) > 1:
        kwds['streaming'] = False
        work = [(run_doctest, (file,), kwds) for file in files]
        pool = multiprocessing.Pool(processes=nthreads)
        for result in pool.imap_unordered(apply, work):
            process_results(result, run_id, postscript, stats)
    
    # Otherwise, do things sequentially.
    else:
        for file in files:
            process_results(run_doctest(file, **kwds), run_id, postscript, stats)
    
    timer.stop()
    if postscript['lines']:
        print '-' * 72
        print "\n".join(postscript['lines'])
        print '-' * 72
    timer.walltime
    print "Total time for all tests: %.1f seconds" % timer.walltime
    print "\tcpu time: %.1f seconds" % postscript['cputime']
    print "\tcumulative wall time: %.1f seconds" % postscript['walltime']
    return stats

def get_basename(path):
    if path is None:
        return None
    path = os.path.abspath(path)
    root = os.path.dirname(path)
    while os.path.exists(os.path.join(root, '__init__.py')):
        root = os.path.dirname(root)
    fully_qualified_path = os.path.splitext(path[len(root) + 1:])[0]
    return fully_qualified_path.replace('/', '.')

class FileDoctestSource(object):
    def __init__(self, path):
        self.path = path
    def create_doctests(self, namespace):
        basename = self.get_basename()
        _, ext = os.path.splitext(os.path.basename(self.path))
        if not basename.startswith('sage.') and ext in ('.py', '.pyx', '.sage', '.spyx'):
            from sage.misc.preparser import load
            load(self.path, namespace)  # TODO - catch errors?
        return extract_doctests_from_source(basename, open(self.path), namespace)
    def get_basename(self):
        return get_basename(self.path)
    def get_file_path(self):
        return self.path

class DatabaseDoctestSource(object):
    def __init__(self, db, path, basename, run_id):
        self.db = db
        self.path = path
        self.basename = basename
        self.run_id = run_id
        
    def create_doctests(self, namespace):
        self.path = self.resolve_path()
        _, ext = os.path.splitext(os.path.basename(self.path or 'unknown.py'))
        if not self.basename.startswith('sage.') and ext in ('.py', '.pyx', '.sage', '.spyx'):
            from sage.misc.preparser import load
            if self.path and os.path.exists(self.path):
                load(self.path, namespace)  # TODO - catch errors?
            else:
                print "Unable to locate", self.path if self.path else self.basename

        conn = dbwrap.DBWrapper(self.db)
        doctest_name = None
        tests = []
        for example in conn.execute("select * from timings where type='example' and run_id=? and basename=?", self.run_id, self.basename):
            example = DictAsObject(example)
            if doctest_name != example.doctest:
                doctest_name = example.doctest
                test = doctest.DocTest([], namespace, example.doctest, example.basename, example.lineno, None)
                tests.append(test)
            if 'want_markings' in example and example.want_markings is not None:
                want = MarkedOutput(example.want).update(**example.want_markings)
            else:
                want = example.want
            example = doctest.Example(example.source, want, example.exc_msg, example.lineno, 0, example.options)
            if example.source.startswith('sage: '):
                example.sage_source = example.source[6:]
                example.source = preparse(example.sage_source)
            tests[-1].examples.append(example)
        return tests

    def resolve_path(self):
        if self.path is None or not os.path.exists(self.path):
            ext_list = (os.path.splitext(self.path)[1],) if self.path else ('.py', '.pyx', '.sage', '.spyx')
            new_path = None
            basename = self.basename
            if '.' in basename:
                try:
                    module_name = basename[basename.rindex('.') + 1:]
                    pkg = __import__(basename[:basename.rindex('.')]).__path__[0]
                    for ext in ext_list:
                        candidate = os.path.join(pkg, module_name + ext)
                        if os.path.exists(candidate):
                            new_path = candidate
                except ImportError:
                    pass
            else:
                for lib_path in sys.path:
                    for ext in ext_list:
                        candidate = os.path.join(lib_path, basename + ext)
                        if os.path.exists(candidate):
                            new_path = candidate
                            break
                    if new_path is not None:
                        break
            if new_path is not None:
                self.path = new_path
        return self.path
        
    def get_file_path(self):
        return self.path
    
    def get_basename(self):
        return self.basename

def run_doctest(info, streaming=None, timeout=500):
    # TODO: Recursively invoke this script with valgrind, etc. if needed
    def run():
        timer = Timer().start()
        import sage.misc.misc
        if str(os.getpid()) not in sage.misc.misc.SAGE_TMP:
            reload(sage.misc.misc)
            reload(sage.misc.all)
        import sage.all_cmdline
        sage_namespace = RecordingDict(sage.all_cmdline.__dict__)
        sage_namespace['__name__'] = '__main__'
        sage_namespace['__package__'] = None

        file = info.get_file_path()
        basename = info.get_basename()
        doctests = info.create_doctests(sage_namespace)
        runner = SageDocTestRunner(SageOutputChecker(), verbose=False, optionflags=doctest.NORMALIZE_WHITESPACE|doctest.ELLIPSIS)
        runner.basename = basename
        for test in doctests:
            runner.run(test)
        runner.filename = file
        runner.summarize(verbose=1)
        timer.stop().annotate(runner)
        return (doctests, runner.results())

    return info.get_file_path() or info.get_basename(), fork_and_run(run, timeout=timeout, streaming=streaming)

def get_version():
    from sage.version import version
    return version

def process_results(results, run_id, postscript, stats):
    try:
        filename, (timeout, return_code, results, output) = results
        basename = get_basename(filename)
        print "sage -t", filename
        if timeout:
            print "\tTimed out!"
            print output
            postscript['lines'].append("sage -t %s # timed out" % (filename,))
            stats[basename] = dict(failed=True, walltime=1e6)
        elif return_code:
            print "\tBad exit:", return_code
            print output
            postscript['lines'].append("sage -t %s # bad exit: %s" % (filename, return_code))
            stats[basename] = dict(failed=True, walltime=1e6)
        else:
            doctests, runner = results
            
            if runner.failures:
                print output
                postscript['lines'].append("sage -t %s # %s doctests failed" % (filename, runner.failures))
                stats[basename] = dict(failed=True, walltime=runner.walltime)
            else:
                stats[basename] = dict(walltime=runner.walltime)
            postscript['cputime'] += runner.cputime
            postscript['walltime'] += runner.walltime

            db = get_db()
            
            # File-level profile data.
            data = dict(path=filename, basename=runner.basename, doctest=runner.basename, run_id=run_id, type='file')
            for attr in ('cputime', 'walltime', 'failures'):
                data[attr] = getattr(runner, attr)
            db.timings.insert(data)
            db.timings.ensure_index(doctest=True)
            db.timings.ensure_index(basename=True)
            
            all = []
            for test in doctests:
                test_data = {
                    'basename': runner.basename,
                    'lineno': test.lineno,
                    'doctest': test.name,
                    'run_id': run_id,
                    'type': 'example',
                }
                doctest_cputime = doctest_walltime = 0
                doctest_total_state = None
                for example in test.examples:
                    # Update doctest info.
                    if doctest_total_state is None:
                        doctest_total_state = example.total_state
                    doctest_cputime += example.cputime
                    doctest_walltime += example.walltime
                    # Update Example info.
                    data = dict(test_data)
                    try:
                        data['source'] = 'sage: ' + example.sage_source
                    except AttributeError:
                        data['source'] = example.source
                    if example.predecessors is not None:
                        data['predecessors'] = sorted(e.sequence_number for e in example.predecessors)
                    data['want'] = str(example.want)
                    if isinstance(example.want, MarkedOutput):
                        data['want_markings'] = example.want.__dict__
                    for attr in ('exc_msg', 'lineno', 'options',
                        'sequence_number', 'cputime', 'walltime', 'total_state', 'doctest_state'):
                        data[attr] = getattr(example, attr)
                    try:
                        data['running_state'] = example.running_state
                    except AttributeError:
                        # Optional timing.
                        pass
                    all.append(data)
                doctest_data = dict(total_state=doctest_total_state,
                                    cputime=doctest_cputime,
                                    walltime=doctest_walltime,
                                    **test_data)
                doctest_data['type'] = 'doctest'
                all.append(doctest_data)
            db.timings.insert(all)
            db.timings.ensure_index(total_state=True)
            db.timings.ensure_index(doctest_state=True)
            db.timings.ensure_index(running_state=True)
            db.timings.ensure_index(run_id=True)
            db.commit()

            print "\t[%s tests, %.1f s]" % (len(all), runner.walltime)

    except:
        import traceback
        traceback.print_exc()

def create_package_timings(db, run_id):
    def empty_data():
        return dict(count=0, cputime=0.0, walltime=0.0, type='package', run_id=run_id)
    summary_data = defaultdict(empty_data)
    for file in db.timings.find(run_id=run_id, type='file'):
        package_list = file['doctest'].split('.')
        # Note that we store each file as a "package" as well for easier analysis.
        for k in range(1, len(package_list) + 1):
            package = '.'.join(package_list[:k])
            data = summary_data[package]
            data['doctest'] = package
            data['count'] += 1
            data['cputime'] += file['cputime']
            data['walltime'] += file['walltime']
    db.timings.insert(summary_data.values())
    db.timings.ensure_columns(('count_', 'walltime_ss', 'cputime_ss'))
    db.execute("update timings set count_=1, walltime_ss=walltime*walltime, cputime_ss=cputime*cputime where run_id=?", run_id)
#    for row in db.timings.find(run_id=run_id, type='package'):
#        print row
    db.commit()

def reconstruct_doctests(sorted_examples):
    basename = None
    test_name = None
    for example in sorted_examples:
        print example
        example = DictAsObject(example)
        if basename != example.basename:
            if basename is not None:
                yield basename, tests
            basename = example.basename
            tests = []
        if test_name != example.doctest:
            test_name = example.doctest
            test = doctest.DocTest([], {}, example.doctest, example.basename, example.lineno, None)
            tests.append(test)
        if 'want_markings' in example and example.want_markings is not None:
            want = MarkedOutput(example.want).update(**example.want_markings)
        else:
            want = example.want
        example = doctest.Example(example.source, want, example.exc_msg, example.lineno, 0, example.options)
        tests[-1].examples.append(example)
    if basename is not None:
        yield basename, tests

db = None
def get_db(path=None):
    global db
    if db is None:
        assert path is not None
        db = dbwrap.DBWrapper(path)
    return db

def expand(pattern):
    for path in glob.glob(pattern):
        if os.path.isdir(path):
            for root, dirs, files in os.walk(path):
                for dir in list(dirs):
                    if dir[0] == '.':
                        dirs.remove(dir)
                for file in files:
                    if os.path.splitext(file)[1] in ('.py', '.pyx', '.sage', '.rst'):
                        yield os.path.join(root, file)
        else:
            yield path

def expand_all(paths):
    for pattern in paths:
        for path in expand(pattern):
            yield path

def filter_doctests(paths):
    db = get_db()
    all = []
    for path in paths:
        if 'nodoctest' in open(path).read(50):
            continue
        elif os.path.exists(os.path.join(os.path.dirname(path), "nodoctest.py")):
            continue
        basename = get_basename(path)
        latest = False and db.timings.find_one(type='file', doctest=basename, fields=["max(run_id)"])
        if latest:
            info = db.timings.find_one(run_id=latest['max(run_id)'])
            if not info['failures']:
                continue
            all.append((-info['walltime'], path))
        else:
            all.append(((-1e9), path))
    all.sort()
    return [a[-1] for a in all]

def load_stats(filename):
    if os.path.exists(filename):
        return json.load(open(filename))
    else:
        return {}

def save_stats(filename, stats):
    try:
        json.dump(stats, open(filename, 'w'))
    except:
        print "Error saving stats to", filename


def main():

    parser = optparse.OptionParser()
    parser.add_option("-r", "--rerun", dest="rerun", default="", help="version, run_id, date", metavar="SQL_CLAUSE")
    parser.add_option("-d", "--database", dest="database", default="timings.db", metavar="/path/to/db.sqlite")
    parser.add_option("-l", "--label", dest="label")
    parser.add_option("-f", "--failed", action="store_true", dest="failed", default=False)
    parser.add_option("-s", "--stats", dest="stats_path", default=os.path.join(os.path.expanduser("~/.sage/timings2.json")))
    (options, args) = parser.parse_args()

    run_id = time.strftime('%Y-%m-%d-%H-%M-%S-') + "%08x" % random.getrandbits(32)
    print "run_id", run_id
    run_data = dict(
        run_id=run_id,
        version=get_version(),
        time=time.strftime('%Y-%m-%d %H:%M:%S'),
        label=options.label,
    )
    db = get_db(options.database)
    if options.rerun:
        conn = db.conn
        clause = parse_clause(options.rerun, conn)
        old_run_id = list(conn.execute("select run_id from timings join runs using (run_id) where %s order by run_id desc limit 1" % clause))[0]['run_id']
        todo = []
        for row in conn.execute("select basename, null as path from timings where run_id=? and type='file' and %s" % clause, (old_run_id, )):
            todo.append(DatabaseDoctestSource(options.database, row['path'], row['basename'], old_run_id))
    else:
        todo = expand_all(args)
        todo = [FileDoctestSource(path) for path in filter_doctests(todo)]
    
    stats = load_stats(options.stats_path)
    if options.failed:
        def is_failure(doctest):
            basename = doctest.get_basename()
            return basename not in stats or stats[basename].get('failed')
        todo = filter(is_failure, todo)
        
    def sort_key(doctest):
        basename = doctest.get_basename()
        default = dict(walltime=0)
        return -stats.get(basename, default).get('walltime'), basename
    todo = [x[1] for x in sorted((sort_key(doctest), doctest) for doctest in todo)]
    #print [x.get_basename() for x in todo]
    print "Doctesting", len(todo), "files."
    
    db.runs.insert(run_data)
    db.runs.ensure_index(time=True)
    db.runs.ensure_index(version=True)
    db.runs.ensure_index(run_id=True)

    stats.update(run_doctests(todo, nthreads=3, streaming=False, run_id=run_id))
    save_stats(options.stats_path, stats)

    create_package_timings(db, run_id)
    db.commit()

if __name__ == "__main__":
    main()
